//
// Created by Crestimes on 2024/11/18.
//

#include "FABuilder.h"

#include <algorithm>
#include <iomanip>
#include <queue>
#include <stack>

#include "global.h"
#include "ReManager.h"

FABuilder::FABuilder(const map<string, string>& reMap, const set<string>& reOfTokenType,
                     const set<string>& reForAuxiliary): finalNFA(0, 0) {
    this->reMap = reMap;
    this->reOfTokenType = reOfTokenType;
    this->reForAuxiliary = reForAuxiliary;
    buildDFAs();
}

/**
 * 构建所有需要生成DFA图的正则表达式的DFA图，初始化allDFAs成员变量
 */
void FABuilder::buildDFAs() {
    for (const auto& res : reMap) {
        // 初始化成员变量
        initBeforeGenerate(res.first);
        // 获取NFA图
        generateNFA();
        // 打印结果NFA图
        printNFAMatrix();
        // 由NFA图得到DFA图
        generateDFA();
        // 打印结果DFA图
        printDFAMatrix();
        // 最小化DFA
        minimizeDFA();
        // 打印最小化DFA图
        printMinDFAMatrix();
        // 保存DFA图
        if (reOfTokenType.count(res.first)) {
            DFAsAndEndsOfTokenType[res.first] = make_pair(minDFANodes, ends);
        }
        else {
            DFAsAndEndsOfAuxiliary[res.first] = make_pair(minDFANodes, ends);
        }
        // 清空数据
        clear();
    }
}

void FABuilder::initBeforeGenerate(const string& reName) {
    // 初始化通用成员变量
    this->reNameNow = reName;
    this->reValueNow = reMap[reName];
    cout << "reName: " << this->reNameNow << endl;
    cout << "reValue: " << this->reValueNow << endl;
}

void FABuilder::generateNFA() {
    // 转后缀表达式
    initSuffixRe();
    // 计算后缀表达式
    calcSuffixRe();
}

/**
 * 将正则表达式转为后缀形式，保存到suffixRe成员变量
 */
void FABuilder::initSuffixRe() {
    for (size_t i = 0; i < reValueNow.length(); i++) {
        if (reValueNow[i] == '\\') {
            if (reValueNow[i + 1] == 'n') {
                // 换行符，特殊处理
                suffixRe.emplace(1, '\n');
                // 保存字符
                symbols.insert("\n");
            }
            else {
                // 转义符号，字符入后缀表达式
                suffixRe.push(string("\\") + reValueNow[i + 1]);
                // 保存字符
                symbols.emplace(1, reValueNow[i + 1]);
            }
            i++; // 跳过下一个字符
        }
        else if (ReManager::isOpr(reValueNow[i])) {
            // 运算符，需要判断优先级
            // 进行出栈操作，直到优先级不大于自己
            if (reValueNow[i] == '|') {
                while (!oprStack.empty() && oprStack.top() != '(' && oprStack.top() != '|') {
                    suffixRe.emplace(1, oprStack.top());
                    oprStack.pop();
                }
            }
            else if (reValueNow[i] == '&') {
                while (!oprStack.empty() && oprStack.top() != '(' && oprStack.top() != '|' && oprStack.top() != '&') {
                    suffixRe.emplace(1, oprStack.top());
                    oprStack.pop();
                }
            }
            // '*' '+' '?'
            oprStack.push(reValueNow[i]);
        }
        else if (reValueNow[i] == ')') {
            // 将栈中的符号出栈，直到遇到左括号
            while (!oprStack.empty() && oprStack.top() != '(') {
                suffixRe.emplace(1, oprStack.top());
                oprStack.pop();
            }
            oprStack.pop(); // 弹出(
        }
        else if (reValueNow[i] == '(') {
            // ( 直接入栈
            oprStack.push(reValueNow[i]);
        }
        else {
            // 字符直接入后缀表达式
            // 可能是某个正则名，需要遍历判断
            bool isReName = false;
            for (const auto& auxRe : reForAuxiliary) {
                if (i + auxRe.length() - 1 < reValueNow.length() && reValueNow.substr(i, auxRe.length()) == auxRe) {
                    // 整个是一个正则名
                    isReName = true;
                    suffixRe.emplace(auxRe);
                    // 保存字符（正则名）
                    symbols.insert(auxRe);
                    // 移动下标
                    i += auxRe.length() - 1;
                    break;
                }
            }
            if (!isReName) {
                // 不是正则名则只放入一个字符即可
                suffixRe.emplace(1, reValueNow[i]);
                // 保存字符
                symbols.emplace(1, reValueNow[i]);
            }
        }
    }
    // 剩余符号进入后缀表达式
    while (!oprStack.empty()) {
        suffixRe.emplace(1, oprStack.top());
        oprStack.pop();
    }
}

/**
 * 计算后缀表达式，构建NFA图
 */
void FABuilder::calcSuffixRe() {
    while (!suffixRe.empty()) {
        string front = suffixRe.front();
        suffixRe.pop();
        if (front[0] == '\\' || !ReManager::isOpr(front[0])) {
            // 是字符，直接入栈
            // 转义字符要去掉转义符号
            if (front[0] == '\\') {
                NFAStack.push(createNFA(front.substr(1)));
            }
            else {
                NFAStack.push(createNFA(front));
            }
        }
        else {
            // 运算符，需要进行运算
            const char op = front[front.length() - 1];
            NFA n1 = NFAStack.top();
            NFAStack.pop();
            // 双目运算符
            if (op == '|') {
                NFA n2 = NFAStack.top();
                NFAStack.pop();
                NFAStack.push(orCalc(n2, n1));
            }
            else if (op == '&') {
                NFA n2 = NFAStack.top();
                NFAStack.pop();
                NFAStack.push(andCalc(n2, n1));
            }
            // 单目运算符
            else if (op == '?') NFAStack.push(whatCalc(n1));
            else if (op == '*') NFAStack.push(mulCalc(n1));
            else if (op == '+') NFAStack.push(plusCalc(n1));
                // error
            else cout << "unexpected op: " + string(1, op);
        }
    }
    // 栈顶NFA即为结果
    finalNFA = NFAStack.top();
    NFAStack.pop();
    // 标记起点和终点集
    start = finalNFA.start;
    ends.insert(finalNFA.end);
}

/**
 * 创建两个点并在两个点之间连线，返回这个NFA
 * @param symbolOnEdge 两个点的边上的字符
 * @return 创建的NFA
 */
NFA FABuilder::createNFA(const string& symbolOnEdge) {
    // 创建两个NFA点
    createTwoNFANodes();
    // 连接两个点
    addNFAEdge(NFANodes.size() - 2, NFANodes.size() - 1, symbolOnEdge);
    // 创建NFA
    return {NFANodes.size() - 2, NFANodes.size() - 1};
}

/**
 * 为NFANodes列表里索引为st和ed的两点添加一条边，边值为symbolOnEdge
 * @param start 起点下标
 * @param end 终点下标
 * @param symbolOnEdge 两个点之间边上的字符
 */
void FABuilder::addNFAEdge(const size_t start, const size_t end, const string& symbolOnEdge) {
    // 创建边
    Edge edge(start, end, symbolOnEdge);
    edges.push_back(edge);
    // 邻接表建边
    edge.next = NFANodes[start].first;
    NFANodes[start].first = &edge;
    // 记录信息用于打印
    NFANodes[start].tableMap[symbolOnEdge].push_back(end);
}

/**
 * 创建两个的NFA节点，保存到NFANodes中
 */
void FABuilder::createTwoNFANodes() {
    NFANodes.emplace_back();
    NFANodes.emplace_back();
}

NFA FABuilder::mulCalc(const NFA& originNFA) {
    // 创建两个点
    createTwoNFANodes();
    const size_t start = NFANodes.size() - 2;
    const size_t end = NFANodes.size() - 1;
    // 连四条线
    addNFAEdge(start, originNFA.start, EPSILON);
    addNFAEdge(start, end, EPSILON);
    addNFAEdge(originNFA.end, end, EPSILON);
    addNFAEdge(originNFA.end, originNFA.start, EPSILON);
    // 返回NFA图
    return {start, end};
}

NFA FABuilder::plusCalc(const NFA& originNFA) {
    // 创建两个点
    createTwoNFANodes();
    const size_t start = NFANodes.size() - 2;
    const size_t end = NFANodes.size() - 1;
    // 连三条线
    addNFAEdge(start, originNFA.start, EPSILON);
    addNFAEdge(originNFA.end, end, EPSILON);
    addNFAEdge(originNFA.end, originNFA.start, EPSILON);
    // 返回NFA图
    return {start, end};
}

NFA FABuilder::whatCalc(const NFA& originNFA) {
    // 创建两个点
    createTwoNFANodes();
    const size_t start = NFANodes.size() - 2;
    const size_t end = NFANodes.size() - 1;
    // 连三条线
    addNFAEdge(start, originNFA.start, EPSILON);
    addNFAEdge(start, end, EPSILON);
    addNFAEdge(originNFA.end, end, EPSILON);
    // 返回NFA图
    return {start, end};
}

NFA FABuilder::orCalc(const NFA& originN1, const NFA& originN2) {
    // 创建两个点
    createTwoNFANodes();
    const size_t start = NFANodes.size() - 2;
    const size_t end = NFANodes.size() - 1;
    // 连四条线
    addNFAEdge(start, originN1.start, EPSILON);
    addNFAEdge(start, originN2.start, EPSILON);
    addNFAEdge(originN1.end, end, EPSILON);
    addNFAEdge(originN2.end, end, EPSILON);
    // 返回NFA图
    return {start, end};
}

NFA FABuilder::andCalc(const NFA& originN1, const NFA& originN2) {
    // 直接将两个NFA连接
    addNFAEdge(originN1.end, originN2.start, EPSILON);
    return {originN1.start, originN2.end};
}

void FABuilder::generateDFA() {
    // 初步构建DFA图
    initDFATemp();
    // 化简DFA图
    initDFA();
}

/**
 * 初步构建DFA图，每个DFA点的内容形如 { + 节点,节点... + }
 */
void FABuilder::initDFATemp() {
    set<string> nodeStringSet; // 多个NFA节点构成的单个DFA节点，使用 { + 节点,节点... + } 的字符串标识
    // 获取初始状态集合
    set<size_t> epsilonSet = findNextE(finalNFA.start);
    queue<set<size_t>> qu;
    qu.push(epsilonSet);
    // 不断迭代
    while (!qu.empty()) {
        set<size_t> front = qu.front();
        qu.pop();
        // 获取集合唯一标识str
        string nodeString = setToStr(front);
        if (nodeString != "{}")nodeStringSet.insert(nodeString);
        // 向该集合尝试所有输入
        for (const string& symbol : symbols) {
            set<size_t> toNodes; // 通过c最终到达的所有点
            for (const size_t i : front) {
                // 获取到通过c到达的所有点
                vector<size_t> toNodesTemp = NFANodes[i].tableMap[symbol];
                // 遍历所有点执行epsilon闭包
                for (size_t j : toNodesTemp) {
                    toNodes.insert(j); // 加入最后的点集
                    epsilonSet = findNextE(j); // epsilon闭包
                    for (size_t k : epsilonSet)toNodes.insert(k); // 加入最后的点集
                }
            }
            // 如果之前没出现过这种集合，就加入最后结果，并且入队继续迭代，否则就舍弃
            string toNodeString = setToStr(toNodes);
            if (toNodeString != "{}" && !nodeStringSet.count(toNodeString)) {
                nodeStringSet.insert(toNodeString);
                qu.push(toNodes);
            }
            // 建立DFA图
            DFANodesTemp[nodeString][symbol] = toNodeString;
        }
    }
}

/**
 * 给DFATemp的点重新配索引，以索引为键而不是像 { + 节点,节点... + } 这样的字符串为键
 */
void FABuilder::initDFA() {
    // 当前DFA图的所有点都是集合的字符串形式，打印出来非常多内容而且难以分析
    // 整个映射
    map<string, size_t> nodeString2Index; // 每个DFA和他对应的新点下标
    string startNodeString; // 用来标记起点字符串，后续会更新为新起点索引
    size_t index = 1; // 下标从1开始（在遍历中会记录起点字符串，会把起点字符串标记为下标0，下标0即起点）
    set<size_t> newEnds; // 换了下标后的新的终点集
    for (const auto& oldNode : DFANodesTemp) {
        // 把first转成set<size_t>
        const string nodeString = oldNode.first;
        set<size_t> st = strToSet(nodeString);
        // 判断是否终点
        for (size_t end : ends) {
            if (st.count(end)) {
                // 记录新的终点
                newEnds.insert(index);
            }
        }
        // 判断是否起点
        if (st.count(start)) startNodeString = nodeString;
        nodeString2Index[nodeString] = index++;
    }
    // 起点换到下标0
    nodeString2Index[startNodeString] = 0;
    start = 0;
    // 该起点也可能是终态，需要判断是否要将新起点索引0补回到ends集合
    const set<size_t> st = strToSet(startNodeString);
    for (size_t ed : ends) {
        if (st.count(ed)) {
            newEnds.insert(0);
        }
    }
    // 更新终点集
    ends = newEnds;
    // 将原DFA图中的每个点(字符串)替换成下标索引，得到新的DFA
    for (const auto& oldNode : DFANodesTemp) {
        map<string, size_t> newDFAMap;
        for (const auto& oldMap : oldNode.second) {
            // 遍历旧的转移图
            if (oldMap.second == "{}") continue; // 因为前面要打印所以里面加了空集，跳过空集
            // 使用nodeString2Index找到要替换的索引，更新到newDFAMap
            newDFAMap[oldMap.first] = nodeString2Index[oldMap.second];
        }
        // 该次遍历的起点也用nodeString2Index找到对应的索引，赋值上面生成的新转移图
        DFANodes[nodeString2Index[oldNode.first]] = newDFAMap;
    }
}

void FABuilder::minimizeDFA() {
    set<size_t> visit; // 标记是否访问过该点
    set<size_t> newEnds; // 新终点集
    map<size_t, size_t> sameTo; // key下标的点等价于value下标的点，后续会将所有key下标的点用value值替代
    for (const auto& i : DFANodes) {
        if (visit.count(i.first)) continue;
        for (const auto& j : DFANodes) {
            // 两重循环两两比较
            if (i.second == j.second) {
                // 如果转移图一模一样
                visit.insert(j.first); // 标记已访问
                sameTo[j.first] = i.first; // j可以用i替代（first是下标索引）
                // 判断要被替代的这个j的索引是否为终态
                if (ends.count(j.first)) {
                    // 是终态，后续被替换成的i的索引也应该是终态，在新终点集中加入i的索引
                    newEnds.insert(i.first);
                }
            }
        }
    }
    // 更新终点集
    ends = newEnds;
    for (const auto& node : DFANodes) {
        if (!minDFANodes.count(sameTo[node.first])) minDFANodes[sameTo[node.first]] = map<string, size_t>();
        for (const auto& toMap : node.second) {
            minDFANodes[sameTo[node.first]][toMap.first] = sameTo[toMap.second];
        }
    }
}

/**
 * 找到下标为index的NFA点的所有通过epsilon相连的点，即求该NFA点的epsilon闭包
 * @param index 下标
 * @return 该NFA点的epsilon闭包结果
 */
set<size_t> FABuilder::findNextE(const size_t index) {
    set<size_t> result;
    queue<size_t> qu;
    qu.push(index);
    while (!qu.empty()) {
        size_t front = qu.front();
        qu.pop();
        result.insert(front);
        for (size_t i : NFANodes[front].tableMap[EPSILON])qu.push(i);
    }
    return result;
}

/**
 * {..} -> set<size_t>
 * @param setString 集合的字符串标识
 * @return 标识对应的集合
 */
set<size_t> FABuilder::strToSet(string setString) {
    setString = setString.substr(1, setString.size() - 2); // 去除{}
    stringstream ss(setString);
    string item;
    set<size_t> st;
    while (getline(ss, item, ',')) {
        // 分割,
        st.insert(strtol(item.c_str(), nullptr, 10));
    }
    return st;
}

/**
 * 清空数据
 */
void FABuilder::clear() {
    set<string>().swap(symbols);
    set<size_t>().swap(ends);
    start = 0;

    stack<char>().swap(oprStack);
    stack<NFA>().swap(NFAStack);
    queue<string>().swap(suffixRe);
    vector<NFANode>().swap(NFANodes);
    vector<Edge>().swap(edges);
    finalNFA = NFA(0, 0);

    map<string, map<string, string>>().swap(DFANodesTemp);
    map<size_t, map<string, size_t>>().swap(DFANodes);

    map<size_t, map<string, size_t>>().swap(minDFANodes);
}

/**
 * 将集合转为字符串标识，用于NFA转DFA的算法中
 * @param epsilonSet epsilon闭包的结果集合
 * @return 集合内容组成的标识字符串
 */
string FABuilder::setToStr(const set<size_t>& epsilonSet) {
    if (epsilonSet.empty())return "{}";
    // 一种集合转换为唯一一种string
    // 先转成数组排序后合成字符串
    vector<size_t> ve(epsilonSet.begin(), epsilonSet.end());
    sort(ve.begin(), ve.end());
    string nodeString = "{" + to_string(ve[0]);
    for (size_t i = 1; i < ve.size(); i++)nodeString += ("," + to_string(ve[i]));
    return nodeString + "}";
}

void FABuilder::printNFAMatrix() {
    symbols.insert(EPSILON); // 打印的时候展示空，打印完成后会移除
    constexpr size_t split = 10; // 打印间隔
    cout << right << setw(split) << "NFA";
    for (const auto& symbol : symbols) {
        // 表头为所有存过的字符和空
        if (symbol == "\n") cout << right << setw(split) << "\\n";
        else cout << right << setw(split) << symbol;
    }
    cout << endl;
    for (size_t i = 0; i < NFANodes.size(); i++) {
        cout << right << setw(split) << i;
        string toNodes;
        for (const auto& symbol : symbols) {
            // 判断该点有没有边的值是c，有就存入边上对应的终点
            if (NFANodes[i].tableMap.count(symbol) && !NFANodes[i].tableMap[symbol].empty()) {
                toNodes = to_string(NFANodes[i].tableMap[symbol][0]);
                for (size_t j = 1; j < NFANodes[i].tableMap[symbol].size(); j++) {
                    toNodes += ',';
                    toNodes += to_string(NFANodes[i].tableMap[symbol][j]);
                }
            }
            // 否则就为空
            else {
                toNodes = '.';
            }
            cout << right << setw(split) << toNodes;
        }
        cout << endl;
    }
    // 打印起点和终点集
    cout << right << setw(split) << "set<st>" << right << setw(split) << start << endl;
    cout << right << setw(split) << "set<ed>";
    for (const auto i : ends) {
        cout << right << setw(split) << i;
    }
    cout << endl << endl;
    symbols.erase(EPSILON);
}

void FABuilder::printDFAMatrix() const {
    constexpr size_t split = 6; // 打印间隔
    cout << right << setw(split) << "DFA";
    for (const auto& symbol : symbols) {
        // 表头为所有存过的字符
        if (symbol == "\n") cout << right << setw(split) << "\\n";
        else cout << right << setw(split) << symbol;
    }
    cout << endl;
    for (auto node : DFANodes) {
        // 包含NFA的终点的就是终点
        cout << right << setw(split) << node.first;
        for (const auto& symbol : symbols) {
            if (node.second.count(symbol))cout << right << setw(split) << node.second[symbol];
            else cout << right << setw(split) << -1;
        }
        cout << endl;
    }
    // 打印起点和终点集
    cout << right << setw(split) << "set<st>" << right << setw(split) << start << endl;
    cout << right << setw(split) << "set<ed>";
    for (const auto i : ends) {
        cout << right << setw(split) << i;
    }
    cout << endl << endl;
}

void FABuilder::printMinDFAMatrix() const {
    constexpr size_t split = 6; // 打印间隔
    cout << right << setw(split) << "MinDFA";
    for (const auto& symbol : symbols) {
        // 表头为所有存过的字符
        if (symbol == "\n") cout << right << setw(split) << "\\n";
        else cout << right << setw(split) << symbol;
    }
    cout << endl;
    for (auto node : minDFANodes) {
        cout << right << setw(split) << node.first;
        for (const auto& symbol : symbols) {
            if (node.second.count(symbol))cout << right << setw(split) << node.second[symbol];
            else cout << right << setw(split) << -1;
        }
        cout << endl;
    }
    // 打印起点和终点集
    cout << right << setw(split) << "set<st>" << right << setw(split) << start << endl;
    cout << right << setw(split) << "set<ed>";
    for (const auto i : ends) {
        cout << right << setw(split) << i;
    }
    cout << endl << endl;
}
